Static timing analysis (STA) is used to compute the expected timing of a digital circuit to identify problem areas of an integrated circuit during the design phase and in advance of actual fabrication. Timing runs in STA simulate the timing of the integrated circuit to determine whether or not the integrated circuit meets various timing constraints and, therefore, is likely to operate properly if fabricated in accordance with the tested design.
Deterministic static timing analysis (DSTA) propagates timing quantities, such as arrival times (ATs), required arrival times (RATs), and slews, along with any other timing related quantities (guard times, adjusts, asserts, etc.), in a timing graph as single valued deterministic data. DSTA covers a single corner of a space of process variations with each individual timing run. A corner represents a particular combination of input values for a parameter that may include temperature of the circuit, input voltage, and various manufacturing parameters of an integrated circuit. To evaluate the impact that a given parameter will have on timing, multiple DSTA timing runs must be executed with parameters that affect timing set at several maximum and minimum corners, such as high and low temperature, high and low voltages, and various processing conditions. For example, DSTA timing runs may compare a worst case corner characterized by a combination of high input voltage, a high operating temperature, and the worst manufacturing parameters with a best case corner characterized by a combination of a low input voltage, a low operating temperature, and the best manufacturing parameters.
Timing values are computed for the timing graph at each node based upon the ATs, which define the time (or the time distribution) at which a given signal arrives at a timing point, and the RATs, which defines the time (or the time distribution) at which the signal is required to get to the timing point, in order to meet the timing requirements. These ATs and RATs are used to compute timing metrics in the form of slacks at nodes (RAT minus AT for late mode and AT minus RAT for early mode). A negative value for either a late mode slack or an early mode slack indicates a timing constraint violation. As a check of the performance of the integrated circuit design, DSTA timing runs may examine many or all of the corners and the integrated circuit design may be iteratively adjusted until all of the corners pass the timing tests. These results reflect the extreme performance bounds of the integrated circuit and may require numerous timing runs to fully explore the space of process variations. Even then, the results may be overly pessimistic and misleading for optimization tools.
Block-based statistical static timing analysis (SSTA) propagates timing quantities as probability distribution functions, or their approximation, instead of as single valued deterministic data under DTSA. Statistical minimum and maximum operations used to calculate a node slack for the propagated statistical distribution functions. Typically, slack data is only collected for timing qualification at a subset of all of the timing graph nodes, sometimes referred to as test points or endpoints, which are frequently defined as those timing graph nodes that are either primary outputs of the circuit, or those that control data propagation (e.g., the input to storage elements, such as latches). Multiple slacks are frequently incident at endpoints because of the backward propagated RAT data from upstream nodes and any timing tests that may be present on those nodes (e.g., setup or hold tests). These slacks may be referred to as edge slacks because they arise from the timing and test segments that form the graph edges incident on the node of interest. The final slack value for that node is defined as the statistical minimum of all edge slacks, as this is the limiting slack that can cause timing failure.
A single timing run using block-based SSTA predicts the performance of the integrated circuit over the entire space of process variations. In contrast, a single timing run using DSTA merely predicts a single corner of the space of process variations. Consequently, in order to close timing, a single SSTA timing run may replace multiple DSTA timing runs. For example, assuming the existence of N parameters (i.e., variables or sources of variation) and two corners per parameter, then 2N corners would have to be individually analyzed by discrete DSTA timing runs to match the effectiveness of a single SSTA run. Hence, SSTA is far more computationally efficient than DSTA.
Block-based SSTA also reduces pessimism as a result of the statistical techniques inherent in this approach. A test run that passes in a single process corner under in a DSTA timing run may actually fail without detection in one or more other performance-limiting corners in the process space, which a SSTA timing run would reveal. SSTA can, therefore, reduce the exaggerated pessimism inherent in DSTA. For example, the propagation of known independently random terms in SSTA allows for taking the square root of the sum of the squares of random quantities (RSSing) between each propagation state, rather than straight summation as in DTSA. Other pessimism relief may occur when sampling the final distributions, as additional RSSing may occur between terms during projection from a distribution to some example sample value. Finally, information regarding the probability of particular failure modes may be obtained in SSTA, as opposed to DSTA that merely indicates a binary pass/fail condition. SSTA may allow for very low probability fails to be ignored while also allowing for a more aggressive clipping of the statistical tails when used with at-speed tests.
In block-based SSTA, the probability distribution functions for many timing quantities in the delay model are approximated in a canonical or first order form. A timing quantity Q is approximated in canonical form at a particular corner, which represents a combination of input values for the parameters p1, . . . pN, by a first-order Taylor series expressed as:
            Q      ⁢              {                              p            1                    ,                      …            ⁢                                                  ⁢                          p              N                                      }              =                  Q        0            +                        ∑                      i            =            1                    N                ⁢                  {                                                    ⅆ                Q                            /                              ⅆ                                  p                  i                                                      *                          (                                                p                  i                                -                                  p                                      i                    ⁢                                                                                  ⁢                    0                                                              )                                }                      ,where Q0 is the nominal value of the timing quantity, and dQ/dpi is the derivative of the timing quantity Q with respect to parameter pi. The nominal value of the timing quantity Q0 is evaluated at a nominal corner characterized by nominal values of the parameters p0=(pi0, . . . pN0). If the variation in the ith parameter pi is treated as a random variable Ri characterized by a zero mean and a unit variance, and the actual parameter pi has a variance equal to σi, the canonical form of the timing quantity Q is equivalent to:
      Q    ⁡          (                        p          1                ,                  …          ⁢                                          ⁢                      p            N                              )        =            Q      0        +                  ∑                  i          =          1                N            ⁢                        {                                                    ⅆ                Q                            /                              ⅆ                pi                                      *                          σ              i                        *                          R              i                                }                .            
Because there are generally multiple different parameters of interest, there are also multiple different dQ/dpi derivatives. The sensitivities (dQ/dpi derivatives) may be computed via forward finite differencing by finding the timing quantity Q at an arbitrary base corner pb and using this base corner in common as one end of each finite difference derivative. If the parameter input values at the base corner pb are equal to (p1b, . . . pNb), and the parameter input values at another corner (pb+Δpi) are equal to (p1b, . . . pib+Δpi, . . . pNb), then dQ/dpi is equal to {Q(pb+Δpi)−Q(pb)}/Δpi.
The base corner pb may have each of the parameter input values at one end of its allowed or reachable range (e.g., pi,min, which might be a negative three sigma point for the parameter), and Δpi is the extent of the reachable range (e.g., pi,max−pi,min). The advantage of using an end of the parameter range at a base corner pb, rather than the parameter mean, is that, in N+1 calculations of the timing quantity Q, derivative estimates may be obtained that reflect the full range of the parameters. Starting at a mean or nominal value of each parameter, 2N+1 calculations of the timing quantity Q, each of which perturbs each parameter pi either above pi0 or below pi0, must be performed. Otherwise, the calculated dQ/dpi derivatives would be based on only half the range of each parameter.
If the base corner pb differs from the nominal corner p0, then the nominal delay D0 should be computed from the base corner pb, rather than by directly computing the delay at the nominal corner p0. Otherwise, the delay D computed by applying the canonical delay equation at the base corner pb may not match the actual base corner delay. Thus, under these circumstances, the canonical form of the delay may be expressed as:
      D    0    =            D      ⁡              (                  p          b                )              +                  ∑                  i          =          1                N            ⁢                        {                                    (                                                p                                      i                    ⁢                                                                                  ⁢                    0                                                  -                                  p                  b                                            )                        *                                          ⅆ                D                            /                              ⅆ                pi                                              }                .            
Delays and slews are particular timing quantities in block-based SSTA that are approximated in canonical form. Each of these quantities depends on various non-timing parameters including, but not limited to, transistor effective lengths (Leff), metal layer widths, temperature, and voltage. In addition, both the delay and output slew of a particular cell in a digital design will depend explicitly on the input slew to that gate. The input slew, as well as the output slew, of a timing signal reflects the slope or transition time of the timing signal. For example, the input slew at a gate may be set equal to the time required for the waveform propagated as the corresponding timing quantity to transition from a multiplicative factor of 0.1 times the supply voltage (Vdd) to a multiplicative factor of 0.9 times Vdd.
Although delay depends on input slew, the input slew itself has a canonical approximation. It may be desirable to eliminate the dependence of the delay on slew to obtain a canonical delay that depends only on other values that are not themselves timing quantities. Conventionally, this feat was accomplished by computing a single derivative of delay, D, with respect to input slew and, then, using chain ruling to eliminate the slew dependence. Thus, the canonical form of the delay can be expressed by:
  D  =            D      0        +                  ∑                  i          =          1                N            ⁢              {                                            ⅆ              D                        /                          ⅆ                              p                i                                              *                      (                                          p                i                            -                              p                                  i                  ⁢                                                                          ⁢                  0                                                      )                          }              +                            ⅆ          D                /                  ⅆ          Slew                    *              (                                            ∑                              i                =                1                            M                        ⁢                          {                                                                    ⅆ                    Slew                                    /                                      ⅆ                                          p                      i                                                                      *                                  (                                                            p                      i                                        -                                          p                                              i                        ⁢                                                                                                  ⁢                        0                                                                              )                                            }                                +                      S            o                          )            
As above, if variation in the ith parameter pi is represented by a random variable Ri(0,1) having a zero mean and a unit standard deviation, this expression is equivalent to:
      D    =                  D        0            +                        ∑                      i            =            1                    N                ⁢                  {                                                    ⅆ                D                            /                              ⅆ                                  p                  i                                                      *                          σ              i                        *                          R              i                                }                    +                                    ⅆ            D                    /                      ⅆ            Slew                          *                  (                                                    ∑                                  i                  =                  1                                M                            ⁢                              {                                                                            ⅆ                      Slew                                        /                                          ⅆ                                              p                        i                                                                              *                                      σ                    i                                    *                                      R                    i                                                  }                                      +                          S              o                                )                      ,where the summation ranges differ because the delay and the input slew may have dependencies on different parameters, and dD/dSlew is computed just like any other delay derivative.
A problem with the use of a single sensitivity value dD/dSlew in the calculation of the delay is that the dependence of the delay on input slew may vary significantly across the parameter space, which may lead to significant errors. In particular, the delay sensitivity to slew can be highly non-linear as a function of process corner.
Accordingly, there is a need for an improved method for statistical slew propagation during block-based SSTA that overcomes these and other deficiencies of conventional block-based SSTA that arise from the non-linearity of the sensitivity of delay to slew.